1. The Field of the Invention
The field of the present invention is that of the proxy servers used in connection with accessing data over the World Wide Web (xe2x80x9cWWWxe2x80x9d) through the Internet or other Wide Area Network (xe2x80x9cWANxe2x80x9d). More particularly, the present invention involves an array of multiple proxy servers configured together to act as a single distributed cache of information identified through the use of Uniform Resource Locators (xe2x80x9cURLxe2x80x9d). Specifically, the invention treats the routing of a URL request received by one array member to the array member having the cached information associated with the URL.
2. Present State of the Art
Generally speaking, the concept of a xe2x80x9ccachexe2x80x9d or xe2x80x9ccachingxe2x80x9d as used in computer terminology and applications typically means making a more accessible copy of some piece of data for a performance advantage. For example, information that is cached is in many instances more accessible than it otherwise would be so that processing speed is increased since accessing the cached information is quicker.
Since having excess copies of data can create its own sort of overhead and because cache size is limited, data is not typically retained in a cache indefinitely and will eventually be overwritten after a certain amount of time if the cache is being fully utilized. This may occur according to a Leased Recently Used (xe2x80x9cLRUxe2x80x9d) algorithm, an expiration time, or any other relevant criteria for a particular application. Caching commonly exists at the microprocessor level with instruction and data caches so as to avoid excessive accessing of system RAM and may also exist elsewhere in a computer system or in a network of computer systems.
Another form of caching is commonly used in relation to accessing data or information over the WWW. A user having Internet access can directly receive a URL identified data object, such as a web page, and then display it locally on a browser. Each time the user receives such a data object, there is a delay as the Hyper Text Transport Protocol (xe2x80x9cHTTPxe2x80x9d) request travels across the Internet to the location identified by the URL and the destination server processing the URL request responds with the requested data object. Because the data object can be quite large, the time to access the data objects with the HTTP request and response creates a significant amount of information traveling over the Internet connection causing delays and excess overhead.
In some organizations, many of the same data objects are requested by the various users within the organization. It is therefore common to introduce a proxy server that will receive user access requests from a client application, such as a web browser. Referring to FIG. 1, the use of a proxy server acting as a cache is shown. A client application 20 will direct all URL requests to a proxy server 21 that will serve as a cache for any information (i.e., URL data objects) associated with the URL. Should the proxy server 21 not have the URL data object within its cache, it will, in turn, make access over the Internet 22 to the destination server found within the URL in order to place the data object into its cache and then respond to the client 20 URL request. Thereafter, should another client make a request to the proxy server 21, it can be serviced directly from the cache without necessary access over the Internet to the destination server found in the URL itself.
Note that the client 20 can be any software application capable of communicating or directing requests to the proxy server 21 using the HTTP protocol and would include other proxy servers, web browsers, Internet xe2x80x9cenabledxe2x80x9d applications, etc. Furthermore, HTTP requests contain a variety of information that can be used to xe2x80x9cforcexe2x80x9d the proxy server 21 to access the URL data object over the Internet in order to assure that the xe2x80x9cfreshestxe2x80x9d copy has been accessed. Such operation of proxy servers and their use as caches is generally known in the art for use in servicing HTTP requests.
It should be noted that the term URL may indicate either the address of where a data object is originally located and accessed, or the data object itself. To distinguish, a URL itself would be an address or location of the data object whereas a URL data object would be the actual web page file that is transmitted across the Internet to the client application. Though the appropriate usage is readily identifiable by context, efforts will be made throughout this application to distinguish between the two as best as possible.
There are benefits of having a proxy server acting as a cache for URL data objects. One benefit is that for cached items, the total access time for a user is generally reduced since the connection between the client 20 and the proxy server 21 is typically over a Local Area Network (xe2x80x9cLANxe2x80x9d) rather than having to access the data object over the Internet or other Wide Area Network (xe2x80x9cWANxe2x80x9d). Another benefit is for security purposes so that an organization may have a xe2x80x9cfirewallxe2x80x9d to protect itself from unwanted outside penetration.
Larger corporations and other organizations may have many proxy servers servicing their needs. It becomes desirable in such situations to harness many proxy servers together as a single, logical distributed cache. Ideally, such a single distributed cache would have no duplication of URL data objects contained therein. Furthermore, a single distributed cache should have as little overhead as possible in servicing any given URL request that arrives at a member of the distributed cache. In other words, the actual URL data object may not be residing at the same server that originally receives the URL request and some form of forwarding, routing, or acquisition of the desired URL data object must occur in order to service that original URL request.
One attempt at creating a such a distributed cache is the Internet Cache Protocol (xe2x80x9cICPxe2x80x9d) that coordinates the activity of an xe2x80x9carrayxe2x80x9d of proxy servers. Though ICP allows an array of proxy servers to function as a distributed cache, it also has some drawbacks as will be explained hereafter.
Referring now to FIG. 2, the interaction of a client with a proxy server array is shown. In such an arrangement, a client 23 will contact one of the proxy servers in the array 24 in order to access URL data objects that are available over the Internet 25. Typically, a client 23 is assigned to a particular proxy server within the proxy server array 24 and may itself be a proxy server. Since the URL data object requested by a client may exist in a different proxy server than the one contacted, a mechanism or protocol is necessary for routing the URL request from the receiving proxy server to the appropriate proxy server, or in some other way service that URL request.
Referring now to FIG. 3, proxy server array that is organized and configured according to the ICP protocol is shown. In the example shown in FIG. 3, a client 26 will direct HTTP requests to an assigned proxy server 27 that is part of an ICP proxy server array 28. Assuming that a desired URL data object is contained in the distributed cache created by the ICP proxy server array 28 and located at the proxy server 29, a scenario illustrating the operation of ICP is now shown. This scenario will also illustrate a number of problems that make ICP a less than optimal way of creating a distributed cache.
The URL request will originate at the client 26 and be received by the proxy server 27 as indicated by arrow 30. After determining that the desired URL object does not reside at the proxy server 27 in its local cache storage, a query will be sent out to all proxy servers in the ICP proxy server array 28 as indicated by the query messages path 32. In turn, every other proxy server that receives the query will give a response back to the proxy server 27 as indicated by the response message path 34. Each individual response will indicate whether or not the specified URL data object resides at that particular responding proxy server. Note that more than one of the proxy servers in the ICP proxy server array 28 may contain a given URL data object.
For purposes of this example, it is assumed that only the proxy server 29 actually contains the data object and therefore the response from proxy server 29 to proxy server 27 would be the only response having an indication that the desired or requested URL data object exists thereon. Note that for an ICP proxy server array 28 of N proxy servers, that Nxe2x88x921 messages were sent out by the proxy server 27 querying for the existence of the URL data object and Nxe2x88x921 messages were sent back to or received by the proxy server 27 in response, thus creating a fair amount of network message traffic and usage of the overall network bandwidth.
Once the proxy server 27 knows where the desired URL data object is located, it will issue a request to get the object as indicated by the get path 36. Naturally, the proxy server 29 will respond by sending the desired URL data object from the proxy server 29 to the proxy server 27 as indicated by the send object path 38. Now that the proxy server 27 has the desired URL data object, it can respond to the original URL request and return that data object to the client 26.
Cache storage redundancy can be seen since the proxy server 27 will also place the URL data object into its local cache such that the same URL data object now exists in both proxy server 27 and proxy server 29. Also, network usage overhead is significant since the total number of messages to allow the proxy server 27 the ability to service the original URL request for an ICP proxy server array 28 of N proxy servers is 2(Nxe2x88x921)+2 total data messages across the network.
Given the above scenario, a number of undesirable problems exhibit themselves almost immediately. First, by using a query-response scenario to contact all of the proxy servers in the ICP proxy server array, a significant amount of network resources may be consumed. Additionally, a natural consequence of the query-response scenario is that the larger the ICP proxy server array 28 becomes the greater the network overhead for each non-resident URL request, therefore adding a negative scalability component to operating an ICP server array. This means that each addition of another proxy server onto the array will in fact increase the amount of communication between the different proxy servers for all array members and for each request in order to resolve the correct location of a desired URL data object. Theoretically, there may exist an upper limit to the number of proxy servers that may be comfortably used in an ICP proxy server array 28.
Another problem is that multiple copies of the distributed cache URL data objects exist across the various proxy servers. In an extreme case, each proxy server of the ICP proxy server array 28 could become a redundant mirror of the other array members. It would be desirable to have only one copy of a URL data object existing in the entire distributed cache so that the distributed cache may be used to its full capacity.
Finally, adding or deleting proxy servers from the ICP proxy server array 28 may totally disrupt the distribution of URL data objects across the entire logical cache. In an extreme case, the distributed cache may be xe2x80x9cemptiedxe2x80x9d upon any addition or removal of a proxy server from a proxy server array.
What is needed is a truly distributed logical cache across an array of proxy servers where a given URL data object is contained therein at only one location so as to maximize cache capacity. Furthermore, what is needed is a way to access the correct proxy server within the logical distributed cache or array of proxy servers without making a query to each and every proxy server making up the array thereby allowing a request received at one proxy server to be directly routed to the correct proxy server, or alternatively, an acquisition of the desired URL data object from the correct proxy server quickly attained. Finally, what is needed is a way of gracefully migrating cached URL data objects between the different proxy servers as a result of additions or removals of proxy servers from the proxy server array making up the distributed cache that will not require the reorientation of all URL data objects in the cache.
It is an object of the present invention to migrate a minimal number of URL data objects between proxy servers in a proxy server array in response to permanent or temporary changes in the array membership.
It is another object of the present invention to utilize deterministic hashing algorithms to allow consistent and predictable identification of a proxy server to be assigned or have residing thereon a particular URL data object.
It is yet another object of the present invention to provide a proxy server array that has a minimal amount of cached URL data object redundancy amongst the local caches of the individual proxy servers making up the array.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
To achieve the foregoing objects, and in accordance with the invention as embodied and broadly described herein a method, computer program product, and system for migrating URLs within a dynamically changing distributed cache of URLs is provided. Migration occurs as URL data objects are assigned to reside in the local cache of different proxy servers due to change in the proxy server array, such as the addition, removal, or temporary unavailability of a member.
Each proxy server has access to the entire array membership information stored in array membership list. This array membership list is periodically updated and reflects changes in array membership due to additions, removals, or temporary unavailability of the various proxy servers that make up the array. When changes have propagated through the proxy server array, all array membership lists at each proxy server will contain identical information. The array membership list is also propagated to enabled clients so that array membership information resides at the client itself.
When a proxy server receives a URL data object request or an enabled client generates a URL data object request, it uses the array membership list, the URL itself, and a deterministic hashing function to identify which array member should actually hold the URL data object in its local cache. The request may then be serviced by accessing the desired data object from the correct proxy server without making expensive query-response transactions over the network. The hashing function operates so as to distribute the cached URL data objects evenly over the entire proxy server array without redundancy so as to more efficiently use the array capacity.
The proxy server identification mechanism works by computing a hash value for each server name found in the array membership list and a hash value for the requested URL. The URL hash value is combined with each member proxy server hash value to form a combined value. The proxy server associated with highest of the combined values is identified as where the desired URL should reside in local cache. A load factor that assigns some proxy servers proportionately more URL data objects for the local cache are also incorporated in the creation of the combined hash values.
All information for making a determination as to the correct proxy server is completely available at a single proxy server receiving the URL request or an enabled client generating a URL request so that no external information is necessary. Furthermore, because of the propagation of array membership information between the proxy servers and all enabled clients, it is the exact same information and will identify the exact same proxy server regardless of which proxy server originally receives the URL request or enabled client generates the URL request.
When a member is removed or temporarily unavailable, the hashing algorithm is designed to redistribute URL requests that were previously directed to the member server equally among the remaining servers. This causes only a fraction of the cache itself to be redistributed, namely, those that were in the removed or temporarily unavailable server""s local cache. In an equally balanced distributed cache of equivalent proxy servers having the same capacity local cache, only 1/N of the URL data objects would be migrated amongst the remaining proxy servers, where N equals the number of proxy servers before the removal.
When a member proxy server is added to the array, the hashing algorithm will redistribute an equal portion of the URL requests from each original member and redistribute them to the newly added member. This causes some URL data objects that were stored in the local caches of the original members to migrate to the local cache of the newly added member. In an equally balanced distributed cache of equivalent proxy servers having the same capacity local cache, only 1/N of the URL data objects would be migrated from the original proxy servers to the new proxy server, where N equals the number of original proxy servers.
In either case, only a minimal amount of URL data object migration occurs. This allows the distributed cache to be dynamically changing with the least amount of cache misses and general disruption.
These and other objects and features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.